class Solution:
    """前两个方法都不对"""
    def maxProfit(self, prices: list) -> int:
        if len(prices) == 0:
            return 0
        buy_price, res_list, max_price = prices[0], [], 0
        for i in range(1, len(prices)):
            max_price = max(max_price, prices[i])
            if prices[i] <= buy_price:
                if max_price - buy_price > 0:
                    res_list.append(max_price - buy_price)
                max_price = 0
                buy_price = prices[i]
        else:
            if max_price - buy_price > 0:
                res_list.append(max_price - buy_price)
        # print(res_list)
        if len(res_list) == 0:
            return 0
        elif len(res_list) == 1:
            buy_price, res_list = prices[0], []
            for i in range(1, len(prices)):
                if prices[i] < prices[i - 1]:
                    res_list.append(prices[i - 1] - buy_price)
                    buy_price = prices[i]
            else:
                if prices[-1] - buy_price > 0:
                    res_list.append(prices[-1] - buy_price)
        if len(res_list) == 1:
            return res_list[0]
        else:
            res_list.sort()
            return res_list[-1] + res_list[-2]

    def maxProfit2(self, prices: list) -> int:
        if len(prices) <= 1:
            return 0
        # elif len(prices) == 2:
        #     if prices[1] - prices[0] > 0:
        #         return prices[1] - prices[0]
        #     else:
        #         return 0
        buy_price, res_list, max_price = prices[0], [], 0
        for i in range(1, len(prices)):
            max_price = max(max_price, prices[i])
            if prices[i] <= buy_price:
                if max_price - buy_price > 0:
                    res_list.append(max_price - buy_price)
                max_price = 0
                buy_price = prices[i]
        else:
            if max_price - buy_price > 0:
                res_list.append(max_price - buy_price)
        if len(res_list) == 0:
            return 0
        elif len(res_list) == 1:
            while 0 in prices:
                prices.remove(0)
            mid_list = prices[:]
            min_num = min(mid_list)
            mid_list.remove(min_num)
            prices[prices.index(min_num)] = min(mid_list)
            buy_price, res_list2, max_price = prices[0], [], 0
            for i in range(1, len(prices)):
                max_price = max(max_price, prices[i])
                if prices[i] <= buy_price:
                    if max_price - buy_price > 0:
                        res_list2.append(max_price - buy_price)
                    max_price = 0
                    buy_price = prices[i]
            else:
                if max_price - buy_price > 0:
                    res_list2.append(max_price - buy_price)
            if len(res_list2) == 0:
                return res_list[0]
            elif len(res_list2) == 1:
                return res_list[0]
            else:
                res_list2.sort()
                return res_list2[-1] + res_list2[-2] + min(mid_list) - min_num
        else:
            res_list.sort()
            return res_list[-1] + res_list[-2]

    def maxProfit3(self, prices: list) -> int:
        """这个也有点小问题,动态规划的状态转移方程在特殊情况下会有问题"""
        if len(prices) <= 1:
            return 0
        prices.append(-1)
        min_num_no_sell = prices[0]
        max_sell_once, min_num_sell_once = 0, prices[0]
        max_finish = 0
        for i in range(1, len(prices)):
            if prices[i] < prices[i - 1]:
                max_finish = max(max_finish, max_sell_once + prices[i - 1] - min_num_sell_once)
                if max_sell_once < prices[i - 1] - min_num_no_sell:
                    min_num_sell_once = prices[i]
                    max_sell_once = prices[i - 1] - min_num_no_sell
                else:
                    min_num_sell_once = min(prices[i], min_num_sell_once)
                min_num_no_sell = min(min_num_no_sell, prices[i])
        return max_finish

    def maxProfit4(self, prices: list) -> int:
        if len(prices) <= 1:
            return 0
        buy1, sell1 = -prices[0], 0
        buy2, sell2 = -prices[0], 0
        for now_price in prices:
            buy1 = max(buy1, -now_price)
            sell1 = max(sell1, buy1 + now_price)
            buy2 = max(buy2, sell1 - now_price)
            sell2 = max(sell2, buy2 + now_price)
        return sell2


a = Solution()
print(a.maxProfit4([7, 1, 5, 3, 6, 4]))  # 7
print(a.maxProfit4([3, 3, 5, 0, 0, 3, 1, 4]))  # 6
print(a.maxProfit4([1, 2, 3, 4, 5]))  # 4
print(a.maxProfit4([7, 6, 4, 3, 1]))  # 0
print(a.maxProfit4([2, 4, 1]))  # 2
print(a.maxProfit4([1, 2, 4, 2, 5, 7, 2, 4, 9, 0]))  # 13
print(a.maxProfit4([1, 2, 4, 2, 5, 7, 1, 4, 2, 9, 0]))  # 14
print(a.maxProfit4([1, 2]))  # 1
print(a.maxProfit4([4, 1, 2]))  # 1
print(a.maxProfit4([1, 2, 7, 4, 11]))  # 13
print(a.maxProfit4([8, 3, 6, 2, 8, 8, 8, 4, 2, 0, 7, 2, 9, 4, 9]))  # 15
print(a.maxProfit4([3, 5, 3, 4, 1, 4, 5, 0, 7, 8, 5, 6, 9, 4, 1]))  # 13
